Start Concurrent: A Gentle Introduction to Concurrent Programming

The processor, or central processing unit (CPU), is the “brain” of a computer. It fetches instructions, decodes them, and executes them. It may send data to or from memory or I/O devices. The CPU on virtually all modern computers is a microprocessor, meaning that all the computation is done by a single integrated circuit fabricated out of silicon. What are the important features of CPUs? How do we measure their speed and power?

Memory is where all the programs and data on a computer are stored. The memory in a computer is usually not a single piece of hardware. Instead, the storage requirements of a computer are met by many different technologies.

At the top of the pyramid of memory is primary storage, memory that the CPU can access and control directly. On desktop and laptop computers, primary storage usually takes the form of random access memory (RAM). It is called random access memory because it takes the same amount of time to access any part of RAM. Traditional RAM is volatile, meaning that its contents are lost when it’s unpowered. All programs and data must be loaded into RAM to be used by the CPU.

After primary storage comes secondary storage, which is dominated by hard drives that store data on spinning magnetic platters. Optical drives (such as CD, DVD, and Blu-ray), flash drives, and the now virtually obsolete floppy drives fall into the category of secondary storage as well. Secondary storage is slower than primary storage, but it is non-volatile. Some forms of secondary storage such as CD-ROM and DVD-ROM are read only, but most are capable of reading and writing.

Before we can compare these kinds of storage effectively, we need to have a system for measuring how much they store. In modern digital computers, all data is stored as a sequence of 0s and 1s. In memory, the space that can hold either a single 0 or a single 1 is called a bit, which is short for “binary digit.”

A bit is a tiny amount of information. For organizational purposes, we call a sequence of eight bits a byte. The word size of a CPU is two or more bytes, but memory capacity is usually listed in bytes not words. Both primary and secondary storage capacities have become so large that it is inconvenient to describe them in bytes. Computer scientists have borrowed prefixes from physical scientists to create suitable units.

Common units for measuring memory are bytes, kilobytes, megabytes, gigabytes, and terabytes. Each unit is 1,024 times the size of the previous unit. Notice that \(2^{10}\) (1,024) is almost the same as \(10^3\) (1,000). Sometimes it is not clear which value is meant. Disk drive manufacturers always use powers of 10 when they quote the size of their disks. Thus, a 1 TB hard disk can hold \(10^{12}\) (1,000,000,000,000) bytes, not \(2^{40}\) (1,099,511,627,776) bytes. Standards organizations have advocated that the terms kibibyte (KiB), mebibyte (MiB), gibibyte (GiB), and tebibyte (TiB) be used to refer to the units based on powers of 2, while the traditional names be used to refer only to the units based on powers of 10, but the new terms have not yet become popular.

We called memory a pyramid earlier in this section. At the top there is a small but very fast amount of memory. As we work down the pyramid, the storage capacity grows but the speed slows down. Of course, the pyramid for every computer is different. Below is a table that shows many kinds of memory moving from the fastest and smallest to the slowest and largest. Effective speed is hard to measure (and is changing as technology progresses), but note that each layer in the pyramid tends to be 10-100 times slower than the previous layer.

I/O devices have much more variety than CPUs or memory. Some I/O devices, such as USB ports, are permanently connected by a printed circuit board to the CPU. Other devices called peripherals are connected to a computer as needed. Their types and features are many and varied, and in this book, we do not go deeply into how to interact with I/O devices.

Common input devices include mice, keyboards, touch pads, microphones, game pads, and drawing tablets. Common output devices include monitors, speakers, and printers. Some devices perform both input and output, such as a network card.

Remember that our view of computer hardware as CPU, memory, and I/O devices is only a model. A PCI Express socket can be considered an I/O device, but the graphics card that fits into the socket can be considered one as well. And the monitor that connects to the graphics card is yet another one. Although the graphics card is an I/O device, it has its own processor and memory, too. It’s pointless to get bogged down in too many details. One of the most important skills in computer science is finding the right level of detail and abstraction to view a given problem.

A number system is a way to represent numbers. It is easy to confuse the numeral that represents the number with the number itself. You might think of the number ten as “10”, a numeral made of two symbols, but the number itself is the concept of ten-ness. You could express that quantity by holding up all your fingers, with the symbol “X”, or by knocking ten times.

Representing ten with “10” is an example of a positional number system, namely base 10. In a positional number system, the position of the digits determines the magnitude they represent. For example, the numeral 3,432 contains the digit 3 twice. The first time, it represents three groups of one thousand. The second time, it represents three groups of ten. (The Roman numeral system is an example of a number system that is not positional.)

The numeral 3,432 and possibly every other normally written number you have seen is expressed in the base 10 or decimal system. It is called base 10 because, as you move from the rightmost digit leftward, the value of each position goes up by a factor of 10. Also, in base 10, ten is the smallest positive integer that requires two digits for representation. Each smaller number has its own digit: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Representing ten requires two existing digits to be combined. Every base has the property that the number it is named after takes two digits to write, namely “1” and “0.” (An exception is base 1, which does not behave like the other bases and is not a normal positional number system.)

The number \(723\) can be written as \(723=7 \times 10^2+2 \times 10^1+3 \times 10^0\).

Note that the rightmost digit is the ones place, which is equivalent to \(10^0\). Be sure to start with \(b^0\) and not \(b^1\) when considering the value of a number written in base \(b\), no matter what \(b\) is. The second digit from the right is multiplied by \(10^1\), and so on. The product of a digit and the corresponding power of 10 tells us how much a digit contributes to the number. In the above expansion, digit 7 contributes 700 to the number 723. Similarly, digits 2 and 3 contribute, respectively, 20 and 3 to 723.

As we move to the right, the power of 10 goes down by one, and this pattern works even for negative powers of 10. If we expand the fractional value 0.324, we get \(0.324=3\times10^{-1}+2\times10^{-2}+4\times10^{-3}\).

We can combine the above two numbers to get \(723.324=7 \times 10^2+2 \times 10^1+ 3\times 10^0+ 3\times10^{-1}+2\times10^{-2}+4\times10^{-3}\).

We can expand these ideas to any base, checking our logic against the familiar base 10. Suppose that a numeral consists of \(n\) symbols \(s_{n-1}, s_{n-2}, \ldots, s_1, s_0\). Furthermore, suppose that this numeral belongs to the base \(b\) number system. We can expand the value of this numeral to:

The leftmost symbol in the numeral is the highest order digit and the rightmost symbol is the lowest order digit. For example, in the decimal numeral 492, 4 is the highest order digit and 2 the lowest order digit.

Fractions can also be expanded in a similar manner. For example, a fraction with \(n\) symbols \(s_{1}, s_{2}, \ldots, s_{n-1}, s_{n}\) in a number system with base \(b\), can be expanded to:

To avoid confusion, the base number is always written in base 10. As computer scientists, we are interested in base 2 because that’s the base used to express numbers inside of a computer. Base 2 is also called binary. The only symbols allowed to represent numbers in binary are “0” and “1”, the binary digits or bits.

In the binary numeral 100110, the leftmost 1 is the highest order bit and the rightmost 0 is the lowest order bit. By the rules of positional number systems, the highest order bit represents \(1 \times 2^5 = 32\).

Examples of numbers written in binary are 100, 111, 0111, and 10101. Recall that the base of the binary number system is 2. Thus, we can write a number in binary as the sum of products of powers of 2. For example, the numeral 10011 can be expanded to:

By expanding the number, we have also shown how to convert a binary numeral into a decimal numeral. Remember that both 10011 and 19 represent the same value, namely nineteen. The conversion between bases changes only the way the number is written. As before, the rightmost bit is multiplied by \(2^0\) to determine its contribution to the binary number. The bit to its left is multiplied by \(2^1\) to determine its contribution, and so on. In this case, the leftmost 1 contributes \(1 \times 2^4 = 16\) to the value.

Another useful number system is base 16, also known as hexadecimal. Hexadecimal is surprising because it requires more than the familiar 10 digits. Numerals in this system are written with 16 hexadecimal digits that include the ten digits 0 through 9 and the six letters A, B, C, D, E, and F. The six letters, starting from A, correspond to the values 10, 11, 12, 13, 14, and 15.

Hexadecimal is used as a compact representation of binary. Binary numbers can get very long, but four binary digits can be represented with a single hexadecimal digit.

39A, 32, and AFBC12 are examples of numbers written in hexadecimal. A hexadecimal numeral can be expressed as the sum of products of powers of 16. For example, the hexadecimal numeral A0BF can be expanded to:

To convert a hexadecimal numeral to decimal, we must substitute the values 10 through 15 for the digits A through F. Now we can rewrite the sum of products from above as:

Thus, we get \(\mathrm{A}0\mathrm{BF}_{16} = 41151_{10}\).

The base 8 number system is also called octal. Like hexadecimal, octal is used as a shorthand for binary. A numeral in octal uses the octal digits 0, 1, 2, 3, 4, 5, 6, and 7. Otherwise the same rules apply. For example, the octal numeral 377 can be expanded to:

You may have noticed that it is not always clear which base a numeral is written in. The digit sequence 337 is a legal numeral in octal, decimal, and hexadecimal, but it represents different numbers in each system. Mathematicians use a subscript to denote the base in which a numeral is written.

Thus, \(337_8 = 255_{10}\), \(377_{10} = 377_{10}\), and \(377_{16} = 887_{10}\). Base numbers are always written in base 10. A number without a subscript is assumed to be in base 10. In Java, there is no way to mark subscripts and so prefixes are used. A prefix of is used for octal, no prefix is used for decimal, and a prefix of is used for hexadecimal. A numeral cannot be marked as binary in Java. The corresponding numerals in Java code would thus be written , , and . Be careful not to pad numbers with zeroes in Java. Remember that the value is not the same as the value in Java.

The following table lists a few characteristics of the four number systems we have discussed with representations of the numbers 7 and 29.

It is often useful to know how to convert a number represented in one base to the equivalent representation in another base. The examples have shown how to convert a numeral in any base to decimal by expanding the numeral in the sum-of-product form and then adding the different terms together. But how do you convert a decimal numeral to another base?

There are at least two different ways to convert a decimal numeral to binary. One way is to write the decimal number as a sum of powers of two as in the following conversion of the number 23.

First, find the largest power of two that is greater than or equal to the number. In this case, 16 fits the bill because 32 is too large. Subtract that value from the number, leaving 7 in this case. Then repeat the process. The last step is to collect the coefficients of the powers of two into a sequence to get the binary equivalent. We used 16, 4, 2, and 1 but skipped 8. If we write a 1 for every place we used and a 0 for every place we skipped, we get \(23=10111_2\). While this is a straightforward procedure for decimal to binary conversion, it can be cumbersome for larger numbers.

An alternate way to convert a decimal numeral to an equivalent binary numeral is to divide the given number by 2 until the quotient is 0 (keeping only the integer part of the quotient). At each step, record the remainder found when dividing by 2. Collect these remainders (which will always be either 0 or 1) to form the binary equivalent. The least significant bit is the remainder obtained after the first division, and the most significant bit is the remainder obtained after the last division.

Let’s use this method to convert 23 to its binary equivalent. The following table shows the steps need for the conversion. The leftmost column lists the step number. The second column contains the number to be divided by 2 at each step. The third column contains the quotient for each step, and the last column contains the current remainder.

We begin by dividing 23 by 2, yielding 11 as the quotient and 1 as the remainder. The quotient 11 is then divided by 2, yielding 5 as the quotient and 1 as the remainder. This process continues until we get a quotient of 0 and a remainder of 1 in Step 5. We now collect the remainders and get the same result as before, \(23 = 10111_2\).

A decimal number can be converted to its hexadecimal equivalent by using either of the two procedures described above. Instead of writing a decimal number as a sum of powers of 2, one writes it as a sum of powers of 16. Similarly, when using the division method, instead of dividing by 2, one divides by 16. Octal conversion is similar.

We use hexadecimal because it is straightforward to convert from it to binary or back. The following table lists binary equivalents for the 16 hexadecimal digits.

With the help of the table above, let’s convert \(3\mathrm{FA}_{16}\) to binary. By simple substitution, \(3\mathrm{FA}_{16} = 0011\mbox{ }1111\mbox{ }1010_2\). Note that we have grouped the binary digits into clusters of 4 bits each. Of course, the leftmost zeroes in the binary equivalent are useless as they do not contribute to the value of the number.

In mathematics, binary numerals can represent arbitrarily big numbers. Inside of a computer, the size of a number is constrained by the number of bits used to represent it. For general purpose computation, 32- and 64-bit integers are the most commonly used. The largest integer that Java represents with 32 bits is 2,147,483,647, which is good enough for most tasks. For larger numbers, Java can represent up to 9,223,372,036,854,775,807 with 64 bits. Java also provides representations for integers using 8 and 16 bits.

These representations are easy to determine for positive numbers: Find the binary equivalent of the number and then pad the left side with zeroes to fill the remaining space. For example, \(19 = 10011_2\). If stored using 8 bits, 19 would be represented as 0001 0011. If stored using 16 bits, 19 would be represented as 0000 0000 0001 0011. (We separate groups of 4 bits for easier reading.)

Recall that computers deal with numbers in their binary representation, meaning that all arithmetic is done on binary numbers. Sometimes it is useful to understand how this process works and how it is similar and different from decimal arithmetic. The table below lists rules for binary addition.

As indicated above, the addition of two 1s leads to a 0 with a carry of 1 into the next position to the left. Addition for numbers composed of more than one bit use the same rules as any addition, carrying values that are too large into the next position. In decimal addition, values over 9 must to be carried. In binary addition, values over 1 must be carried. The next example shows a sample binary addition. To simplify its presentation, we assume that integers are represented with 8 bits.

Let’s add the numbers 60 and 6 in binary. Using the conversion techniques described above, we can find that \(60 = 111100_2\) and \(6 = 110_2\). Inside the computer, these numbers would already be in binary and padded to fill 8 bits.

The result is no surprise, but note that the addition can proceed in binary without conversion to decimal at any point.

Subtraction in binary is also similar to subtraction in decimal. The rules are given in the following table.

When subtracting a 1 from a 0, a 1 is borrowed from the next left position. The next example illustrates binary subtraction.

Again, we’ll use 60 and 6 and their binary equivalents given above.

Negative integers are also represented in computer memory as binary numbers, using a system called two’s complement. When looking at the binary representation of a signed integer in a computer, the leftmost (most significant) bit will be 1 if the number is negative and 0 if it is positive. Unfortunately, there’s more to finding the representation of a negative number than flipping this bit.

Suppose that we need to find the binary equivalent of the decimal number \(-12\) using 8-bits in two’s complement form. The first step is to convert 12 to its 8-bit binary equivalent. Doing so we get 12 = 0000 1100. Note that the leftmost bit of the representation is a 0, indicating that the number is positive. Next we take the two’s complement of the 8-bit representation in two steps. In the first step, we flip every bit, i.e., change every 0 to 1 and every 1 to 0. This gives us the one’s complement of the number, 1111 0011. In the second step, we add 1 to the one’s complement to get the two’s complement. The result is 1111 0011 + 1 = 1111 0100.

Thus, the 8-bit, two’s complement binary equivalent of -12 is 1111 0100. Note that the leftmost bit is a 1, indicating that this is a negative number.

Let us convert -29 to its binary equivalent assuming that the number is to be stored in 8-bit, two’s complement form. First we convert positive 29 to its 8-bit binary equivalent, \(29 =\) 0001 1101.

Next we obtain the one’s complement of the binary representation by flipping 0s to 1s and 1s to 0s. This gives us 1110 0010. Finally, we add 1 to the one’s complement representation to get 1110 0010 + 1 = 1110 0011, which is the desired binary equivalent of -29.

Let us now convert the 8-bit, two’s complement value 1000 1100 to decimal. We note that the leftmost bit of this number is 1, making it a negative number. Therefore, we reverse the process of making a two’s complement. First, we subtract 1 from the representation, yielding 1000 1100 - 1 = 1000 1011. Next, we flip all the bits in this one’s complement form, yielding 0111 0100.

Now we convert this binary representation to its decimal equivalent, yielding 116. Thus, the decimal equivalent of 1000 1100 is -116.

Why do we use two’s complement? First of all, we needed a system that could represent both positive and negative numbers. We could have simply used the leftmost bit as a sign bit and represented the rest of the number as a positive binary number. Doing so would require a check on the bit and some conversion for negative numbers every time a computer wanted to perform an addition or subtraction.

Because of the way it’s designed, positive and negative integers stored in two’s complement can be added or subtracted without any special conversions. The leftmost bit is added or subtracted just like any other bit, and values that carry past the leftmost bit are ignored. Two’s complement has an advantage over one’s complement in that there is only one representation for zero. The next example shows two’s complement in action.

We’ll add -126 and 126. If you perform the needed conversions, their 8-bit, two’s complement representations are 1000 0010 and 0111 1110.

As expected, the sum is 0.

Now, let’s add the two negative integers -126 and -2, whose 8-bit, two’s complement representations are 1000 0010 and 1111 1110.

The result is -128, which is the smallest negative integer that can be represented in 8-bit two’s complement.

When performing an arithmetic or other operation on numbers, an overflow is said occur when the result of the operation is larger than the largest value that can be stored in that representation. An underflow is said to occur when the result of the operation is smaller than the smallest possible value.

Both overflows and underflows lead to wrapped around values. For example, adding two positive numbers together can result in a negative number or adding two negative numbers together can result in a positive number.

Let’s add the numbers 124 and 6. Their 8-bit, two’s complement representations are 0111 1100 and 0000 0110.

This surprising result happens because the largest 8-bit two’s complement integer is 127. Adding 124 and 6 yields 130, a value larger than this maximum, resulting in overflow with a negative answer.

The smallest (most negative) number that can be represented in 8-bit two’s complement is -128. A result smaller than this will result in underflow. For example, -115 - 31 = 110. Try out the conversions needed to test this result.

Although we will most commonly manipulate numbers using traditional mathematical operations such as addition, subtraction, multiplication, and division, there are also operations that work directly on the binary representations of the numbers. Some of these operators are equivalent to mathematical operations, and some are not.

Bitwise AND, bitwise OR, and bitwise XOR take two integer representations and combine them to make a new representation. In bitwise AND, each bit in the result will be a 1 if both of the original integer representations in that position are 1 and 0 otherwise. In bitwise OR, each bit in the result will be a 1 if either of the original integer representations in that position are 1 and 0 otherwise. In bitwise XOR, each bit in the result will be a 1 if the two bits of the original integer representations in that position are not the same and 0 otherwise.

Bitwise complement is a unary operator like the negation operator (). Instead of just changing the sign of a value (which it will also do), its result has every 1 in the original representation changed to 0 and every 0 to 1.

The signed left shift, signed right shift, and unsigned right shift operators all create a new binary representation by shifting the bits in the original representation a certain number of places to the left or the right. The signed left shift moves the bits to the left, padding with 0s, but does not change the sign bit. If you do a signed left shift by \(n\) positions, it is equivalent to multiplying the number by \(2^n\). The signed right shift moves the bits to the right, padding with whatever the sign bit is. If you do a signed right shift by \(n\) positions, it is equivalent to dividing the number by \(2^n\) (with integer division). The unsigned right shift moves the bits to the right, including the sign bit, filling the left side with 0s. And unsigned right shift will always make a value positive but is otherwise similar to a signed right shift. A few examples follow.

Here are a few examples of the result of bitwise operations. We will assume that the values are represented using 32-bit two’s complement, instead of using 8-bit values as before. In Java, bitwise operators automatically convert smaller values to 32-bit representations before proceeding.

Let’s consider the result of \(21 \& 27\).

Note how this result is different from \(21 | 27\).

And also from \(21 \land 27\).

Ignoring overflows, signed left shifting is equivalent to repeated multiplications by 2. Consider 11 << 3. The representation 0000 0000 0000 0000 0000 0000 0000 1011 is shifted to the left to make 0000 0000 0000 0000 0000 0000 0101 1000 \(= 88 = 11\times 2^3\).

Signed right shifting is equivalent to repeated integer divisions by 2. Consider -104 >> 2. The representation 1111 1111 1111 1111 1111 1111 1001 1000 is shifted to the right to make 1111 1111 1111 1111 1111 1111 1110 0110 \(= -26 = -104\div 2^2\).

Unsigned right shifting is the same as signed right shifting except when it is done on negative numbers. Since their sign bit is replaced by 0, an unsigned right shift produces a (generally large) positive number. Consider -104 >>> 2. The representation 1111 1111 1111 1111 1111 1111 1001 1000 is shifted to the right to make 0011 1111 1111 1111 1111 1111 1110 0110 \(= 1,073,741,798\).

Because of the way two’s complement is designed, bitwise complement is equivalent to negating the sign of the number and then subtracting \(1\). Consider ~(-104). The representation 1111 1111 1111 1111 1111 1111 1001 1000 is complemented to 0000 0000 0000 0000 0000 0000 0110 0111 \(= 103\).

We have seen how to represent positive and negative integers in computer memory. In this section we see how rational numbers, such as 12.33, -149.89, and 3.14159, can be converted into binary and represented.

Scientific notation is closely related to the way a computer represents a rational number in memory. Scientific notation is a tool for representing very large or very small numbers without writing a lot of zeroes. A decimal number in scientific notation is written \(a\times 10^b\) where \(a\) is called the mantissa and \(b\) is called the exponent.

For example, the number 3.14159 can be written in scientific notation as \(0.314159\times 10^1\). In this case, \(0.314159\) is the mantissa, and \(1\) is the exponent. Here a few more examples of writing numbers in scientific notation.
\(\begin{array}{ l c l} 3.14159&=&3.14159\times 10^0\\ 3.14159&=&314159\times 10^{-5}\\ -141.324&=&-0.141324\times10^2\\ 30,000&=& .3\times10^5\\ \end{array}\)
There are many ways of writing a number in scientific notation. A more standardized way of writing real numbers is normalized scientific notation. In this notation, the mantissa is always written as a number whose absolute value is less than 10 but greater than or equal to 1. Following are a few examples of decimal numbers in normalized scientific notation.
\(\begin{array}{ l c l} 3.14159&=&3.14159\times 10^0\\ -141.324&=&-1.41324\times10^3\\ 30,000&=& 3.0\times10^4\\ \end{array}\)
A shorthand for scientific notation is E notation, which is written with the mantissa followed by the letter `E' followed by the exponent. For example, 39.2 in E notation can be written \(3.92\mathrm{E}1\) or \(0.392\mathrm{E}2\). The letter `E' should be read ``multiplied by 10 to the power.'' E notation can be used to represent numbers in scientific notation in Java. Instead of writing the number in Java code, or could be used instead.

A rational number can be broken into an integer part and a fractional part. In the number 3.14, 3 is the integer part, and .14 is the fractional part. We have already seen how to convert the integer part to binary. Now we will see how to convert the fractional part into binary. We can then combine the binary equivalents of the integer and fractional parts to find the binary equivalent of a decimal real number.

A decimal fraction \(f\) is converted to its binary equivalent by successively multiplying it by 2. At the end of each multiplication step, either a 0 or a 1 is obtained as an integer part and is recorded separately. The remaining fraction is again multiplied by 2 and the resulting integer part recorded. This process continues until the fraction reduces to zero or enough binary digits for the desired precision have been found. The binary equivalent of \(f\) then consists of the bits in the order they have been recorded, as shown in the next example.

Let’s convert 0.8125 to binary. The table below shows the steps to do so.

We then collect all the integer parts and get 0.1101 as the binary equivalent of 0.8125. We can convert this binary fraction back into decimal to verify that it is correct.

In some cases, the process described above will never have a remainder of 0. In such cases we can only find an approximate representation of the given fraction as demonstrated in the next example.

Let us convert 0.3 to binary assuming that we have only five bits in which to represent the fraction. The following table shows the five steps in the conversion process.

Collecting the integer parts we get 0.01001 as the binary representation of 0.3. Let’s convert this back to decimal to see how accurate it is.

Five bits are not enough to represent 0.3 fully. In this case, we have an error of \(0.3 - 0.28125=0.01875\). Most computers use many more bits to represent fractions and obtain much better accuracy in their representation.

Now that we understand how integers as well as fractions can be converted from one number base to another, we can convert any rational number from one base to another. The next example demonstrates one such conversion.

Let’s convert 14.3 to binary assuming that we will only use six bits to represent the fractional part. First we convert 14 to binary using the technique described earlier. This gives us \(14 = 1110_{2}\). Taking the method outlined in Example  one step further, our six bit representation of 0.3 is 0.010011. Combining the two representations gives \(14.3_{10} = 1110.010011_{2}\).

Floating point notation is a system used to represent rational numbers in computer memory. In this notation a number is represented as \(a\times b^{e}\), where \(a\) gives the significant digits (mantissa) of the number and \(e\) is the exponent. The system is very similar to scientific notation, but computers usually have base \(b = 2\) instead of \(10\).

For example, we could write the binary number 1010.1 in floating point notation as \(10.101\times 2^2\) or as \(101.01\times2^1\). In any case, this number is equivalent to 10.5 in decimal.

In standardized floating point notation, \(a\) is written so that only the most significant non-zero digit is to the left of the decimal point. Most computers use the IEEE 754 floating point notation to represent rational numbers. In this notation, the memory to store the number is divided into three segments: one bit used to mark the sign of the number, \(m\) bits to represent the mantissa (also known as the significand), and \(e\) bits to represent the exponent.

In IEEE floating point notation, numbers are commonly represented using 32 bits (known as single precision) or using 64 bits (known as double precision). In single precision, \(m = 23\) and \(e = 8\). In double precision, \(m = 52\) and \(e = 11\). To represent positive and negative exponents, the exponent has a bias added to it so that the result is never negative. This bias is 127 for single precision and 1,023 for double precision. The packing of the sign bit, the exponent, and the mantissa is shown in Figure 5 (a) and (b).

The following is a step-by-step demonstration of how to construct the single precision binary representation in IEEE format of the number 10.5.

We now have the three components of 10.5 in binary. The memory representation of 10.5 is shown in Figure 5 (c). Note in the figure how the sign bit, the exponent, and the mantissa are packed into 32 bits.

Fixing the number of bits used for representing a real number limits the numbers that can be represented in computer memory using the floating point notation. The largest rational number that can be represented in single precision has an exponent of 127 (254 after bias) with a mantissa consisting of all 1s:
0 1111 1110 1111 1111 1111 1111 1111 111
This number is approximately \(3.402\times10^{38}\). To represent the smallest (closest to zero) non-zero number, we need to examine one more complication in the IEEE format. An exponent of 0 implies that the number is unnormalized. In this case, we no longer assume that there is a 1 bit to the left of the mantissa. Thus, the smallest non-zero single precision number has its exponent set to 0 and its mantissa set to all zeros with a 1 in its 23\(^{\mathrm{rd}}\) bit:
0 0000 0000 0000 0000 0000 0000 0000 001
Unnormalized single precision values are considered to have an exponent of -126. Thus, the value of this number is \(2^{-23} \times 2^{-126} = 2^{-149} \approx 1.4 \times 10^{-45}.\) Now that we know the rules for storing both integers and floating point numbers, we can list the largest and smallest values possible in 32- and 64-bit representations in Java as shown in the following table. Note that largest means the largest positive number for both integers and floating point values, but smallest means the most negative number for integers and the smallest positive non-zero value for floating point values.

Using the same number of bits, floating point representation can store much larger numbers than integer representation. However, floating point numbers are not always exact, resulting in approximate results when performing arithmetic. Always use integer formats when fractional parts are not needed.

Several binary representations in the floating point notation correspond to special numbers. These numbers are set aside and not used for results in normal computation.

As we have seen, many rational numbers can only be approximately represented in computer memory. Thus, arithmetic done on the approximate values yields approximate answers. For example, 1.3 cannot be represented exactly using a 32-bit value. In this case, the product \(1.3\times 3.0\) will be 3.8999999 instead of 3.9. This error will propagate as additional operations are performed on previous results. The next example illustrates this propagation of errors when a sequence of floating point operations are performed.

Suppose that the price of several products is to be added to determine the total price of a purchase at a cash register that uses floating point arithmetic. For simplicity, let’s assume that all items have a price of $1.99. We don’t know how many items will be purchased ahead of time and simply add the price of each item until all items have been scanned at the register. The table below shows the value of the total cost for different number of items purchased.

The first column in the table above is the number of items. The second column is the correct cost of all items purchased. The third column is the cost calculated by adding each item using single precision floating point addition. The fourth and fifth columns give the absolute and relative errors, respectively, of the calculated value. Note how the error increases as the number of additions goes up. In the last row, the absolute error is almost two dollars.

While the above example may seem unrealistic, it does expose the inherent dangers of floating point calculations. Although the errors are much less when using double precision representations, they still exist.

Multicore systems have impressive performance. The first multicore processors had two cores, but current designs have four, six, or eight, and much greater numbers are expected. A processor with eight cores can execute eight different programs at the same time. Or, when faced with a computationally intense problem like matrix math, code breaking, or scientific simulation, a processor with eight cores could solve the problem eight times as fast. A desktop processor with 100 cores that can solve a problem 100 times faster is not out of reach.

In fact, modern graphics cards are already blazing this trail. Consider the 1080p standard for high definition video, which has a resolution of 1,920 \(\times\) 1,080 pixels. Each pixel (short for picture element) is a dot on the screen. A screen whose resolution is 1080p has 2,073,600 dots. To maintain the illusion of smooth movement, these dots should be updated around 30 times per second. Computing the color for more than 2 million dots based on 3D geometry, lighting, and physics effects 30 times a second is no easy feat. Some of the cards used to render computer games have hundreds or thousands of cores. These cores are not general purpose or completely independent. Instead, they’re specialized to do certain kinds of matrix transformations and floating point computations.

Although chip-makers have spent a lot of money marketing multicore technology, they have not spent much money explaining that one of the driving forces behind the ``multicore revolution'' is a simple failure to make processors faster in other ways. In 1965, Gordon Moore, one of the founders of Intel, remarked that the density of silicon microprocessors had been doubling every year (though he later revised this to every two years), meaning that twice as many transistors (computational building blocks) could fit in the same physical space. This trend, often called Moore’s Law, has held up reasonably well. For years, clever designs relying on shorter communication times, pipelining, and other schemes succeeded in doubling the effective performance of processors every two years.

At some point, the tricks became less effective and exponential gains in processor clock rate could no longer be maintained. As clock frequency increases, the signal becomes more chaotic, and it becomes more difficult to tell the difference between the voltages that represent 0s and 1s. Another problem is heat. The energy that a processor uses is related to the square of the clock rate. This relationship means that increasing the clock rate of a processor by a factor of 4 will increase its energy consumption (and heat generation) by a factor of 16.

The legacy of Moore’s Law lives on. We are still able to fit more and more transistors into tinier and tinier spaces. After decades of increasing clock rate, chip-makers began using the additional silicon density to make processors with more than one core instead. Since 2005 or so, increases in clock rate have stagnated.

Does a processor with eight cores solve problems eight times as fast as its single core equivalent? Unfortunately, the answer is, “Almost never.” Most problems are not easy to break into eight independent pieces.

For example, if you want to build eight houses and you have eight construction teams, then you probably can get pretty close to completing all eight houses in the time it would have taken for one team to build a single house. But what if you have eight teams and only one house to build? You might be able to finish the house a little early, but some steps necessarily come after others: The concrete foundation must be poured and solid before framing can begin. Framing must be finished before the roof can be put on. And so on.

Like building a house, most problems you can solve on a computer are difficult to break into concurrent tasks. A few problems are like painting a house and can be completed much faster with lots of concurrent workers. Other tasks simply cannot be done faster with more than one team on the job. Worse, some jobs can actually interfere with each other. If a team is trying to frame the walls while another team is trying to put the roof onto unfinished walls, neither will succeed, the house might be ruined, and people could get hurt.

On a desktop computer, individual cores generally have their own level 1 cache but share level 2 cache and RAM. If the programmer isn’t careful, he or she can give instructions to the cores that will make them fight with each other, overwriting the memory that other cores are using and potentially crashing the program or giving an incorrect answer. Imagine if different parts of your brain were completely independent and fought with one another. The words that came out of your mouth might be random and chaotic and make no sense to your listener.

To recap, the first problem with concurrent programming is finding ways to break down problems so that they can be solved faster with multiple cores. The second problem is making sure that the different cores cooperate so that the answer is correct and makes sense. These are not easy problems, and many researchers are still working on finding better ways to do both.

Some educators believe that beginners will be confused by concurrency and should wait until later courses to confront these problems. We disagree: Forewarned is forearmed. Concurrency is an integral part of modern computation, and the earlier you get introduced to it, the more familiar it will be.